/**
 * 队列是一种列表,不同的是队列只能在队尾插入元素,在队首删除元素。
 * 队列用于存储按 顺序排列的数据,先进先出,这点和栈不一样,在栈中,最后入栈的元素反而被优先处 理。
 * 可以将队列想象成在银行前排队的人群,排在最前面的人第一个办理业务,
 * 新来的人 只能在后面排队,直到轮到他们为止。
 * 队列是一种先进先出(First-In-First-Out,FIFO)的数据结构。
 * 队列被用在很多地方,比如 提交操作系统执行的一系列进程、打印任务池等,
 * 一些仿真系统用队列来模拟银行或杂货 店里排队的顾客。
 */

/**
 * enqueue 元素入队，在队尾添加一个元素
 * dequeue 出队，删除队首元素
 * front 获取队头元素
 * last  获取队尾的元素
 * toString
 * clear 清空
 * empty 判断队列是否为空
 * author ubuntuvim
 * website http://ibeginner.sinaapp.com
 */
function Queue() {
	this.dataStore = [];
	this.enqueue = enqueue;  //入队
	this.dequeue = dequeue;
	this.front = front;
	this.last = last;  
	this.toString = toString;
	this.empty = empty;
	this.length = length;
}

/**
 * 借助push函数实现
 * @param e 入队的元素
 */
function enqueue(e) {
	this.dataStore.push(e);
}

/**
 * 出队
 * 借助shifte函数实现
 * @return 出栈的元素
 */
function dequeue() {
	return this.dataStore.shift();
}


/**
 * 获取队首元素 
 * @return 队首元素
 */
function front() {
	return this.dataStore[0];
}

/**
 * 获取队尾元素 
 * @return 队尾元素
 */
function last() {
	return this.dataStore[this.dataStore.length - 1];
}

/**
 * 显示队列所有元素 
 * @return元素组成的字符串
 */
function toString() {
	var s = "";
	for (var i = 0; i < this.dataStore.length; i++) {
		s += (this.dataStore[i] + "\n");
	}

	return s;
}

/**
 * 判断队列是否为空
 * @return true-空；false-非空
 */
function empty() {
	if (0 == this.dataStore.length)
		return true;
	else
		return false;
}

/**
 * 获取栈的长度
 * @return 栈的长度
 */
function length() {
	return this.dataStore.length;
}

// 测试
// var queue = new Queue();
// queue.enqueue("first element");
// queue.enqueue("ubuntuvim");
// queue.enqueue("nba");
// queue.enqueue("kebi");
// queue.enqueue("jomes");

// // 显示所有元素
// print(queue.toString());
// print("Front of queue is " + queue.front());
// print("Last of queue is " + queue.last());

// print("test dequeue = " + queue.dequeue());
// =================================
// 使用队列:方块舞的舞伴分配问题
//  定义舞者对象
function Dancer(name, sex) {
	this.name = name;
	this.sex = sex;
}

/**
 *  初始化数据
 * @param maleDancers 男性舞者队列
 * @param femaleDancers 女性舞者队列
 */
function getDancers(maleDancers, femaleDancers) {
	var names = read("dencer.txt").split('\n');
	for (var i = 0; i < names.length; i++) {
		names[i] = names[i].trim();  //去掉空格
	}
	// 分割出文件里的性别和姓名
	for (var i = 0; i < names.length; i++) {
		var dcs = names[i].split(' ');
		var name = dcs[1];
		var sex = dcs[0];
		// console.log('sex = ' + sex);
		if ('F' == sex) {
			femaleDancers.enqueue(new Dancer(name, sex));
		} else {
			maleDancers.enqueue(new Dancer(name, sex));
		}
	}
	// print("init data ...");
	// print("femaleDancers len = " + femaleDancers.dataStore.length);
}


/**
 *  跳舞程序
 * @param males 男性舞者
 * @param females 女性舞者
 */
function dance(males, females) {
	print("The dance partners are : \n");
	while (!males.empty() && !females.empty()) {
		var fl = females.dequeue();
		putstr("Females dancer is " + fl.name);
		var m = males.dequeue();
		putstr(" and the male dancer is "+ m.name);

		print("\n");
	}
}


// 测试
var mqueue = new Queue();
var fqueue = new Queue();
getDancers(mqueue, fqueue);

dance(mqueue, fqueue);
//  已经能配对的跳舞的已经全部出栈，剩下的在栈内的是没法配对的
// if (!fqueue.empty()) {
// 	print(fqueue.front().name + " is waiting to dance.");
// }
// if (!mqueue.empty()) {
// 	print(mqueue.front().name + " is waiting to dance.");
// }

//  显示在等待的舞者
if (mqueue.length() > 0) {
	print("There are " + mqueue.length() + " males dancers waitind to dance.");
}
if (fqueue.length() > 0) {
	print("There are " + fqueue.length() + " females dancers waitind to dance.");
}
print("\n\n\n");

// =====================================
// 5.4 使用队列对数据进行排序  基数排序
/*
对于 0~99 的数字,基数排序将数据集扫描两次。
第一次按个位上的数字进行排序,
第二 次按十位上的数字进行排序。
每个数字根据对应位上的数值被分在不同的盒子里。

比如： 91, 46, 85, 15, 92, 35, 31, 22
经过基数排序第一次扫描之后,数字被分配到如下盒子中:
     Bin 0:
     Bin 1: 91, 31
     Bin 2: 92, 22
     Bin 3:
     Bin 4:
     Bin 5: 85, 15, 35
     Bin 6: 46
     Bin 7:
     Bin 8:
     Bin 9:
根据盒子的顺序,对数字进行第一次排序的结果如下:
     91, 31, 92, 22, 85, 15, 35, 46
然后根据十位上的数值再将上次排序的结果分配到不同的盒子中:
     Bin 0:
     Bin 1: 15
     Bin 2: 22
     Bin 3: 31, 35
     Bin 4: 46
     Bin 5:
     Bin 6:
     Bin 7:
     Bin 8: 85
     Bin 9: 91, 92
最后,将盒子中的数字取出,组成一个新的列表,该列表即为排好序的数字:
	15, 22, 31, 35, 46, 85, 91, 92
*/
function distribute(nums, queues, n, digit) {
	for (var i = 0; i < n; i++) {
		if (digit == 1) {  //  个位数
			queues[nums[i] % 10].enqueue(nums[i]);
		} else {
			queues[Math.floor(nums[i] / 10)].enqueue(nums[i]);
		}
	}
}

function collect(queueList, nums) {
	var i = 0;
	for (var digit = 0; digit < 10; digit++) {  // 一共有10个数字，需要10个队列存放
		while (!queueList[digit].empty()) {
			nums[i++] = queueList[digit].dequeue();
		}
	}
}

function displayArray(arr) {
	for (var i = 0; i < arr.length; i++) {
		putstr(arr[i] + " ");
	}
}

var queueList = [];
//  创建10个队列
for (var i = 0; i < 10; i++) {
	queueList[i] = new Queue();
}
var nums = [];  //需要排序的数组
//  随机生成10个数字
for (var i = 0; i < 10; i++) {
	//  Math.random()得到0.0 ~ 1.0 之间的一个伪随机数。
	// Math.floor向下取整
	nums[i] = Math.floor(Math.random() * 101);
}
print("Befor sort : ");
displayArray(nums);
print("\n");
// 排序个位数
distribute(nums, queueList, 10, 1);
collect(queueList, nums);
print("After sort single digit : ");
displayArray(nums);
print("\n");

// 按十位排序
distribute(nums, queueList, 10, 10);
collect(queueList, nums);
print("After sort ten digit : ");
displayArray(nums);
print("\n");





